package com.example.leetcode.top145;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @author dangwen1
 * @date 2022年01月13日 11:23
 * @description
 */
public class TwoSum {
    public static void main(String[] args) {
//        int[] nums = new int[] {3,2,4};
//        twoSum(nums, 6);
        int[] nums = new int[] {2,7,11,15};
//        System.out.println(JSON.toJSONString(twoSum3(nums,9)));
        System.out.println(JSON.toJSONString(twoSum4(nums,9)));
    }
    // 暴力查找法（线性查找法）
    // 固定第一个元素，往后面找目标值减去第一个元素的值，如果第一个没有，则从第二个找起，以此类推。时间复杂度：n^2，空间复杂度：1
    public static int[] twoSum2(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++){
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    System.out.println(i + "," + j);
                }
            }
        }
        return null;
    }

    // hash查找法
    public static int[] twoSum(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    /**
     * leetcode:167
     * @param nums
     * @param target
     * @return 二分查找法(数组已经是有序的)（时间复杂度nlogn）
     */
    public static int[] twoSum3(int[] nums, int target){
        for (int i = 0; i < nums.length; i++) {
            int value = nums[i];
            int index = binarySearch(nums, i + 1, nums.length - 1, target - value);
            if (index != -1){
                return new int[]{i + 1, index + 1};
            }
        }
        return new int[0];
    }

    public static int binarySearch(int[] nums, int begin, int end, int target){
        while (begin <= end){
            int mid = begin + (end - begin)/2;
            if (target == nums[mid]){
                return mid;
            }else if (nums[mid] < target){
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

    /**
     * leetcode:167
     * @param nums
     * @param target
     * @return 双指针搜索法，能有效的所见时间复杂度空间复杂度，是二分查找法的优化方案(时间复杂度n)
     */
    public static int[] twoSum4(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            if (nums[left] + nums[right] == target){
                return new int[]{left + 1, right + 1};
            } else if (nums[left] + nums[right] > target){
                right --;
            } else {
                left++;
            }
        }
        return new int[0];
    }

    /**
     * leetcode:653
     */
    public void twoSum5(){
        List<List<Integer>> list = new ArrayList<>();
    }
}
